package com.msb.advanced.归并;

import java.util.Arrays;

public class Code01_MergeSort {

	
	public static void mergeSortNew(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		doProcess(arr, 0, arr.length - 1);
	}
	
	public static void doProcess(int[] arr, int start, int end) {
		if (start >= end) {
			return;
		}
		//  3, 2, 1, 0
		int mid = start + (end - start) / 2;
		doProcess(arr, start, mid);
		doProcess(arr, mid + 1, end);
		mergeNew(arr, start, mid, end);
	}
	
	public static void mergeNew(int[] arr, int start, int mid, int end) {
		int left = start;
		int right = mid + 1;
		int[] temp = new int[end - start + 1];
		int i = 0;
		while(left <= mid && right <= end) {
			temp[i++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
		}
		while(left <= mid) {
			temp[i++] = arr[left++];
		}
		while(right <= end) {
			temp[i++] = arr[right++];
		}
		for(int num : temp) {
			arr[start++] = num;
		}
	}

	public static void mergeSort1(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process(0, arr.length - 1, arr);
	}
	
	public static void process(int start, int end, int[] arr) {
		if (start >= end) {
			return;
		}
//		int mid = start - ((start - end) >> 1);
		int mid = start + ((end - start) >> 1);
		process(start, mid, arr);
		process(mid + 1, end, arr);
		merge(arr, start, mid, end);
	}
	
	public static void merge(int[] arr, int start, int mid, int end) {
		int[] temp = new int[end - start + 1];
		// 上数
		int left = start;
		int right = mid + 1;
		int i = 0;
		while (left <= mid && right <= end) {
			temp[i++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
		}
		// 剩余
		while (left <= mid) {
			temp[i++] = arr[left++];
		}
		while (right <= end) {
			temp[i++] = arr[right++];
		}
		// 替换
		for (int num : temp) {
			arr[start++] = num;
		}
	}

	public static void mergeSort2(int[] arr) {
		if(arr == null || arr.length < 2) {
			return;
		}
		int step = 1;
		while(step < arr.length) {
			int left = 0;
			int right = Math.min((left + 2 * step - 1), (arr.length - 1));
			while (left <= arr.length - 1) {
				int mid = Math.min(left + step - 1, arr.length - 1);
				merge(arr, left, mid, right);
				left = right + 1;
				right = Math.min((left + 2 * step - 1), (arr.length - 1));
			}
			if (arr.length / 2 < step) {
				break;
			}
			step *= 2;
		}
	}
	
	public static void mergeSort4(int[] arr) {
		int length = arr.length;
		if (arr == null || length < 2) {
			return;
		}
		int step = 1;
		// 1, 2, 3
		while(step < length) {
			int right = length - 1;
			while(right >= 0) {
				int left = Math.max(0, right - step - step + 1);
				int mid = Math.max(0, right - step);
				merge(arr, left, mid, right);
				right =  left - 1;
			}
			if (step > arr.length / 2) {
				break;
			}
			step *= 2;
		}
	}
	
	public static void mergeSort5(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		int length = arr.length;
		int step = 1;
		while(step < length) {
			int right = length - 1;
			while (right >=0) {
				int left = Math.max(0, right - step - step + 1);
				int mid = Math.max(0, right - step);
				merge(arr, left, mid, right);
				right = left - 1;
			}
			if (step > length / 2) {
				break;
			}
			step *= 2;
		}
	}
	
	public static void mergeSort6(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		int length = arr.length;
		process(arr, 0, length - 1);
	}

	public static void process(int[] arr, int start, int end) {
		if (start >= end) {
			return;
		}
		int mid =  ((end - start) >> 1) + start;
		process(arr, start, mid);
		process(arr, mid + 1, end);
		merge(arr, start, mid, end);
	}
	
	public static void mergeSort7(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process1(arr, 0, arr.length - 1);
	}
	
	public static void process1(int[] arr, int start, int end) {
		if (start >= end) {
			return;
		}
		int mid = start + (end - start) / 2;
		process1(arr, start, mid);
		process1(arr, mid + 1, end);
		merge(arr, start, mid, end);
	}
	
	public static void mergeSort8(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 步长
		int end = arr.length;
		int step = 1;
		while (step < end) {
			int right = end - 1;
			while (right >=0) {
				int left = Math.max(0, right - step - step + 1);
				int mid = Math.max(0, right - step);
				merge(arr, left, mid, right);
				right = left - 1;
			}
			// 4 / 2, 5/ 4
			if (step > end / 2) {
				break;
			}
			step *= 2;
		}
		// 某个步长逆序扫一遍
		// 指针左移
		// 步长防越界地政
	}
	
	
	
	// 非递归方法实现
//	public static void mergeSort2(int[] arr) {
//		if (arr == null || arr.length < 2) {
//			return;
//		}
//		int N = arr.length;
//		// 步长
//		int mergeSize = 1;
//		while (mergeSize < N) { // log N
//			// 当前左组的，第一个位置
//			int L = 0;
//			while (L < N) {
//				if (mergeSize >= N - L) {
//					break;
//				}
//				int M = L + mergeSize - 1;
//				int R = M + Math.min(mergeSize, N - M - 1);
//				merge(arr, L, M, R);
//				L = R + 1;
//			}
//			// 防止溢出
//			if (mergeSize > N / 2) {
//				break;
//			}
//			mergeSize <<= 1;
//		}
//	}

	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}

	// for test
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	// for test
	public static void printArray(int[] arr) {
		System.out.println(Arrays.toString(arr));
	}

	// for test
//	public static void main(String[] args) {
//		int testTime = 500000;
//		int maxSize = 100;
//		int maxValue = 100;
//		System.out.println("测试开始");
//		for (int i = 0; i < testTime; i++) {
//			int[] arr1 = generateRandomArray(maxSize, maxValue);
//			int[] arr2 = copyArray(arr1);
//			mergeSort1(arr1);
//			mergeSort8(arr2);
//			if (!isEqual(arr1, arr2)) {
//				System.out.println("出错了！");
//				printArray(arr1);
//				printArray(arr2);
//				break;
//			}
//		}
//		System.out.println("测试结束");
//	}

	public static void main(String[] args) {
		int[] arr = new int[] {2, 1,0, 5};
		mergeSortNew(arr);
		System.out.println(Arrays.toString(arr));
	}
}
